package com.mlh.dp.old;
/*
*题目：一个机器人位于一个 m x n 网格的左上角
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角
问总共有多少条不同的路径？
举例：
输入：m = 3, n = 7
输出：28
* */
public class RobotWalk2 {
    //初始位置1,1  目标位置m,n
    //int sitem,int siten 表示机器人所在位置
    //暴力递归
    public static int method1(int m,int n,int sitem,int siten){
        if(sitem==m&&siten==n){
            return 1;
        }
        if(sitem==m){
            return method1(m,n,sitem,siten+1);
        }
        if(siten==n){
            return method1(m,n,sitem+1,siten);
        }
        return method1(m,n,sitem+1,siten)+method1(m,n,sitem,siten+1);
    }

    //矩阵的含义是机器人所在位置到最终位置的路径数
    //记忆搜索
    public static int method2(int m,int n,int sitem,int siten,int[][]arr){
        if(arr[sitem][siten]!=-1){
            return  arr[sitem][siten];
        }
        if(sitem==m&&siten==n){
            arr[sitem][siten]=1;
            return  arr[sitem][siten];
        }
        if(sitem==m){
            arr[sitem][siten]=1;
            return arr[sitem][siten];
        }
        if(siten==n){
            arr[sitem][siten]=1;
            return arr[sitem][siten];
        }
        arr[sitem][siten]=method1(m,n,sitem+1,siten)+method1(m,n,sitem,siten+1);
        return  arr[sitem][siten];
    }

    //通过分析记忆搜索，退出表依赖
    //严格表依赖
    public static int method3(int m, int n){
        int[][]res=new int[m+1][n+1];
        for(int i=0;i<res.length;i++){
            for(int j=0;j<res[0].length;j++){
                res[i][j]=-1;
            }
        }
        for(int i=1;i<res.length;i++){
            res[i][n]=1;
        }
        for(int i=1;i<res[0].length;i++){
            res[m][i]=1;
        }

        for(int i=m-1;i>=1;i--){
            for(int j=n-1;j>=1;j--){
                res[i][j]=res[i+1][j]+res[i][j+1];
            }
        }
        return res[1][1];
    }
}
